package com.learn._5tree;

import com.learn._3stack.SimpleStack;

public class TreeTraverse {


    public static void main(String[] args) {

        TreeNode<Integer> root = new TreeNode<>();
        root.value = 1;

        TreeNode num2 = new TreeNode();
        root.left = num2;
        num2.value = 2;

        TreeNode num3 = new TreeNode();
        root.right = num3;
        num3.value = 3;

        TreeNode num4 = new TreeNode();
        num2.left = num4;
        num4.value = 4;

        TreeNode num5 = new TreeNode();
        num3.right = num5;
        num5.value = 5;


        //traverseQianRecursive(root);
        //traverseZhongRecursive(root);
        //traverseHouRecursive(root);


        //traverseQian(root);
        traverseZhong(root);
        //traverseHou(root);

    }




    private static class TreeNode<T>{
        T value;
        TreeNode<T> left;
        TreeNode<T> right;
    }





    private static <T>void traverseQianRecursive(TreeNode<T> root){

        if(root == null){
            return;
        }

        System.out.println(root.value);

        traverseQianRecursive(root.left);
        traverseQianRecursive(root.right);
    }

    private static <T>void traverseQian(TreeNode<T> root){

        SimpleStack<TreeNode<T>> stack = new SimpleStack<>();

        TreeNode<T> tmp = root;
        while(tmp != null || stack.size() > 0){

            if(tmp != null){
                while(tmp.left != null){
                    System.out.println(tmp.value);
                    stack.push(tmp);
                    tmp = tmp.left;
                }
                System.out.println(tmp.value);
            }else{
                tmp = stack.pop();
                //System.out.println(tmp.value);
            }

            tmp = tmp.right;

        }


    }


    private static <T>void traverseZhongRecursive(TreeNode<T> root){
        if(root == null){
            return;
        }
        traverseZhongRecursive(root.left);
        System.out.println(root.value);
        traverseZhongRecursive(root.right);
    }

    private static <T>void traverseZhong(TreeNode<T> root){

        SimpleStack<TreeNode<T>> stack = new SimpleStack<>();

        TreeNode<T> tmp = root;
        while(tmp != null || stack.size() > 0){

            if(tmp != null){
                while(tmp.left != null){
                    //System.out.println(tmp.value);
                    stack.push(tmp);
                    tmp = tmp.left;
                }
                System.out.println(tmp.value);
            }else{
                tmp = stack.pop();
                System.out.println(tmp.value);
            }

            tmp = tmp.right;

        }


    }


    private static <T>void traverseHouRecursive(TreeNode<T> root){
        if(root == null){
            return;
        }
        traverseHouRecursive(root.left);
        traverseHouRecursive(root.right);
        System.out.println(root.value);
    }


    private static <T>void traverseHou(TreeNode<T> root){

        SimpleStack<TreeNode<T>> stack = new SimpleStack<>();
        SimpleStack<TreeNode<T>> res = new SimpleStack<>();

        TreeNode<T> tmp = root;
        boolean circle = false;
        while(tmp != null || stack.size() > 0 ){

            if(tmp != null){
                while(tmp.left != null){
                    //System.out.println(tmp.value);
                    stack.push(tmp);
                    tmp = tmp.left;
                }
                System.out.println(tmp.value);
                circle = true;
            }else{
                if(!circle){
                    System.out.println(res.pop().value);
                }
                tmp = stack.pop();
                res.push(tmp);
                circle = false;
                //System.out.println(tmp.value);
            }

            tmp = tmp.right;

        }

        while(res.size() > 0){
           System.out.println(res.pop().value);
        }


    }







}
